package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/5 21:52
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 */
public class Sword13 {

    static int count;

    public static int movingCount(int m, int n, int k) {
        count = 0;
        boolean[][] visited = new boolean[m][n];
        dfs(m, n, 0, 0, k , visited);
        return count;
    }

    private static void dfs(int m, int n, int i, int j, int k, boolean[][] visited) {
        if (i >= m || j >= n || visited[i][j]) {
            return;
        }
        //计算位数和
        int sum = getSum(i, j);
        if (sum > k) {
            return;
        }
        count++;
        visited[i][j] = true;
        //行扩展
        dfs(m, n, i, j + 1, k, visited);
        //列
        dfs(m, n, i + 1, j, k, visited);
    }

    private static int getSum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i = i / 10;
        }
        while (j != 0) {
            sum += j % 10;
            j = j / 10;
        }
        return sum;
    }


    public static void main(String[] args) {
        movingCount(16, 8, 4);
        System.out.println();
        System.out.println(count);
    }
}
